package sort;

import java.util.Arrays;

/**
 * @author huangxin
 * @date 2019/6/24-21:05
 * shell排序
 * 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，
 * 每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止
 */
public class ShellSort {

    public static void shell(int[] arr) {
        int insertIndex;
        int insertValue;

        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
//                insertIndex = i;
////                insertValue = arr[insertIndex];
////                if (arr[insertIndex] < arr[insertIndex - gap]) {
////                    while (insertIndex - gap >= 0 && insertValue < arr[insertIndex - gap]) {
////                        arr[insertIndex] = arr[insertIndex - gap];
////                        insertIndex -= gap;
////                    }
////                    arr[insertIndex] = insertValue;
////                }
//                遍历各组中所有元素,共gap组
                insertIndex = i;
                insertValue = arr[insertIndex];
                if (arr[insertIndex-gap]>insertValue){
                    while (insertIndex - gap >= 0 && insertValue < arr[insertIndex - gap]) {//前面必须有元素且比要插入的元素大
                        arr[insertIndex] = arr[insertIndex - gap];//把大的元素后移
                        insertIndex -= gap;//要插入的下标
                    }
                    arr[insertIndex] = insertValue;//插入元素
                }

            }
        }
//        int gap = arr.length/2;
//        while (true){
//            for (int i = 0; i < gap; i++) {
//                for (int j = i+gap; j<arr.length ; j+=gap) {
//                    insertIndex= j;
//                    insertValue= arr[j];
//                    for (int k = j-gap; k  >=0; k-=gap) {
//                        if (arr[k]>insertValue){
//                            arr[k + gap] = arr[k];//元素后移一位
//                            insertIndex = k;//记录要插入的位置
////                            arr[j]=arr[k];
////                            arr[k] =insertValue;
//                        }
//                    }
//
//                    if (insertIndex!=j){
//                        arr[insertIndex] = insertValue;
//                    }
//                }
//            }
//            System.out.println("希尔排序"+Arrays.toString(arr));
//
//            if (gap==1){
//                break;
//            }
//            gap = gap/2;
//        }

    }
}
